
//1287.有序数组中出现次数超过25%的元素
class Solution {
public:
    int findSpecialInteger(vector<int>& arr) {
        int i=0,n=arr.size();
        int target=n/4;
        while(i<n)
        {
            int pos=upper_bound(arr.begin()+i,arr.end(),arr[i])-arr.begin();  //通过二分查找下一个位置
            if(pos-i>target) return arr[i];    //区间大于25%直接返回

            i=pos;  //区间小于%25据继续找区间
        }
        return -1;
    }
};